import java.util.concurrent.ThreadLocalRandom;

/**
 * @author lilongkang
 * @version 1.0
 * @description: 归并排序：分治+递归思想
 * @date 2024/4/24 0:34
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] array = new int[50];
        for (int i = 0; i < array.length; i++) {
            array[i] = ThreadLocalRandom.current().nextInt(0, 100);
        }

        System.out.println("排序前：");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+",");
        }
        System.out.println();

        sort(array);

        System.out.println("排序后：");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+",");
        }
    }

    public static void sort(int[] array) {
        sortSection(array, 0, array.length - 1);
    }

    private static void sortSection(int[] array, int start, int end) {
        // 只有一个数组元素时终止递归。
        if (start == end) {
            return;
        }
        int mid = (start + end) / 2;
        sortSection(array, start, mid);
        sortSection(array, mid + 1, end);
        merge(array, start, mid + 1, end);
    }

    private static void merge(int[] array, int start1, int start2, int end) {
        int length1 = start2 - start1;
        int[] temp = new int[length1];
        System.arraycopy(array, start1, temp, 0, length1);

        int p1 = 0;
        int p2 = start2;
        for (int i = start1; i <= end; i++) {
            if (temp[p1] <= array[p2]) {
                array[i] = temp[p1];
                p1++;
                if (p1 == length1) {
                    break;
                }
            } else {
                array[i] = array[p2];
                p2++;
                if (p2 > end) {
                    while (p1 < length1) {
                        i++;
                        array[i] = temp[p1];
                        p1++;
                    }
                }
            }
        }
    }
}
